package leetcode_1501_1600;

import java.util.TreeSet;

public class LeeCode_1522 {
    public static void main(String[] args) {
        System.out.println(maxDistance(new int[]{5, 4, 3, 2, 1, 1000000000}, 2));
    }
    private static int maxDistance(int[] position, int m) {
        int n = position.length;
        TreeSet<Integer> set = new TreeSet<>();
        for (int pos : position) {
            set.add(pos);
        }
        int l = 1, r = (set.last() - set.first() + m - 2) / (m - 1);
        while (l < r){
            int mid = (l + r + 1) / 2;
            if (check(set, mid, m - 1)){
                l = mid;
            }else {
                r = mid - 1;
            }
        }
        return l;
    }
    private static boolean check(TreeSet<Integer> set, int d, int m){
        int now = set.first();
        while (m > 0){
            int goal = now + d - 1;
            Integer higher = set.higher(goal);
            if (higher == null)
                return false;
            now = higher;
            m--;
        }
        return true;
    }
}